﻿
namespace ZuoAlgorithms.Class001;

// 测试链接 : https://leetcode.cn/problems/sort-an-array/
public class LanguageConversion
{

    #region 归并排序

    public static int[] SortArray(int[] arr)
    {
        if (arr.Length > 1)
            MergoSort(arr);
        return arr;
    }

    public static int MAXN = 50001;
    public static int[] help = new int[MAXN];
    public static void MergoSort(int[] arr)
    {
        int n = arr.Length;
        for (int l, m, r, step = 1; step < n; step <<= 1)
        {
            l = 0;
            while (l < n)
            {
                m = l + step - 1;
                if (m + 1 >= n)
                {
                    break;
                }
                r = Math.Min(1 + (step << 1) - 1, n - 1);
                Merge(arr, l, m, r);
                l = r + 1;
            }
        }
    }

    public static void Merge(int[] arr, int l, int m, int r)
    {
        int p1 = l;
        int p2 = m + 1;
        int i = l;
        while (p1 <= m && p2 <= r)
        {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m)
        {
            help[i++] = arr[p1++];
        }
        while (p2 <= r)
        {
            help[i++] = arr[p2++];
        }
        for (i = l; i <= r; i++)
        {
            arr[i] = help[i];
        }

    }

    #endregion

    #region 随机快速排序

    public static void QuickSort(int[] arr)
    {
        Sort(arr, 0, arr.Length - 1);
    }

    public static void Sort(int[] arr, int l, int r)
    {
        if (l >= r)
            return;
        Random rand = new Random();
        int x = arr[l + (int)(rand.Next(0, 101) * (r - l + 1))];
        Partition(arr, l, r, x);
        int left = first;
        int right = last;
        Sort(arr, l, left - 1);
        Sort(arr, right + 1, r);
    }

    public static int first, last;
    public static void Partition(int[] arr, int l, int r, int x)
    {
        first = l;
        last = r;
        int i = l;
        while (l <= last)
        {
            if (arr[i] == x)
            {
                i++;
            }
            else if (arr[i] < x)
            {
                Swap(arr, first++, i++);
            }
            else
            {
                Swap(arr, i, last--);
            }
        }
    }

    public static void Swap(int[] arr, int i, int j)
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    #endregion

    #region 堆排序

    public static void HeapSort(int[] arr)
    {
        int n = arr.Length;
        for (int i = n - 1; i >= 0; i--)
        {
            Heapify(arr, i, n);
        }
        while (n > 1)
        {
            Swap(arr, 0, --n);
            Heapify(arr, 0, n);
        }
    }

    public static void HeapInsert(int[] arr, int i)
    {
        while (arr[i] > arr[(i - 1) / 2])
        {
            Swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    public static void Heapify(int[] arr, int i, int s)
    {
        int l = i * 2 + 1;
        while (l < s)
        {
            int best = l + 1 < s && arr[l + 1] > arr[l] ? l + 1 : 1;
            best = arr[best] > arr[i] ? best : i;
            if (best == i)
            {
                break;
            }
            Swap(arr, best, i);
            i = best;
            l = i * 2 + 1;
        }
    }

    #endregion

}
